package leetcode;

public class Lc240 {

    public boolean searchMatrix(int[][] matrix, int target) {
        return binarySearch(matrix, target, 0, 0, matrix.length - 1, matrix[0].length - 1);
    }

    private boolean binarySearch(int[][] matrix, int target, int x1, int y1, int x2, int y2) {
        if (x2 - x1 <= 1 && y2 - y1 <= 1) {
            for (int i = x1; i <= x2; i++) {
                for (int j = y1; j <= y2; j++) {
                    if (matrix[i][j] == target)
                        return true;
                }
            }
        }
        int midx = (x1 + x2) / 2;
        int midy = (y1 + y2) / 2;
        if (matrix[x1][y1] <= target && target <= matrix[midx][midy]) {
            if (binarySearch(matrix, target, x1, y1, midx, midy))
                return true;
        }
        if ((midy + 1 <= y2) && matrix[x1][midy + 1] <= target && target <= matrix[midx][y2]) {
            if (binarySearch(matrix, target, x1, midy + 1, midx, y2 )) {
                return true;
            }
        }
        if ((midx + 1 <= x2) && matrix[midx + 1][y1] <= target && target <= matrix[x2][midy]) {
            if (binarySearch(matrix, target, midx, y1, x2, midy)) {
                return true;
            }
        }

        if ((midx + 1 <= x2) && (midy + 1 <= y2) && matrix[midx + 1][midy + 1] <= target && target <= matrix[x2][y2]) {
            if (binarySearch(matrix, target, midx + 1, midy + 1, x2, y2)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Lc240 lc240 = new Lc240();
        int[][] m = new int[][]{
                {1}
        };
        System.out.println(lc240.searchMatrix(m, 1));
    }



}
